/*
https://leetcode.cn/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/description/
并查集

*/

// 初始化操作
void init() {
    // 使得每一个节点的父节点都是自己
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
}

// 寻找祖宗节点操作
int find(int x) {
    /*
    正常写法：
    if (x == father[x]) return x; // 如果父节点是自己，说明还没有和别的节点连接，祖宗节点就是自己
    else return find(father[x]); // 如果父节点不是自己，就顺着自己的父节点往源头递归查找
    */

    // 以下代码经过简化+路径压缩
    // 路径压缩：将当前节点直接指向其祖宗节点，减少后续查找的时间
    return x == father[x] ? x : (father[x] = find(father[x]));
}

// 连接两个节点的操作
void join(int x, int y) {
    x = find(x); // 找到 x 的祖宗节点
    y = find(y); // 找到 y 的祖宗节点

    // 如果两者的祖宗节点相同，就不用再连接
    if (x == y) return;

    // 如果不同，就把两个祖宗节点连接
    father[y] = x; // 将 y 的祖宗节点设置为 x 的祖宗节点
}

// 判断两个节点是否有相同祖宗节点的操作
bool same(int x, int y) {
    x = find(x); // 找到 x 的祖宗节点
    y = find(y); // 找到 y 的祖宗节点

    // 如果两者祖宗节点相同，返回 true；否则返回 false
    return x == y;
}